1. Field of the Invention
The present invention relates to methods and apparatus for removing noise from digital images, such as for example, digitized photographic images or computer generated images ("CGI") and more particularly to scratches in, or debris on, old motion picture and still photographic films, as well as special effects wires, or supports, used for special effects in motion picture scenes. The present invention further relates to noise induced into digital images due to transmission errors, or malfunctions of image recording or scanning equipment. The present invention also relates to program storage devices for the methods of the present invention, and to recording medium having recorded thereon digital data prepared using the methods of the present invention.
2. Description of the Related Art
With the growing proliferation of available channels for television broadcast and the increasing use of multimedia viewing platforms, many older motion picture and still frame films are likely to see increased use through transfers to video and digital formats. Unfortunately, many old motion and still photographic films have, over the years of use and viewing, become scratched or dirtied with dust or other debris. Since high definition and digital television formats, as well as other digital multimedia formats, will allow imperfections, such as scratches or debris on the film stock, to be quite noticeable to viewers, there is an increasing need for a method of removing scratches from digitized images without degrading or otherwise adversely affecting the perceived quality of the image.
In motion pictures, for example, certain special effects require actors, models or objects in a scene to be suspended or supported via a wire, cable, rod or the like or so as to create the effect of, for example the actor, model or object floating aloft. Typically, the appearance of these wires, cables, rods etc. is later removed from visibility in the scene during post production via optical processing or, more typically these days, via digital processing of the digitized film. Similarly in desktop publishing it is often desirable to remove unwanted portions of an image or erase scratches or blemishes from photographs. It should be noted that the usage of the term "scratch" or "scratch noise" as used herein, is intended to include all of the above noted types of noise which may occur in a digitized image.
A scratch in a digitized image presents itself as unwanted pixels in the digitized image. Scratch noise typically consists of a plurality of contiguous pixels rather than small isolated groups, or clusters, of pixels. In a digitized image, scratch noise may consist of an area of pixels of, for example, 10 pixels.times.100 pixels, and may fall in an area of the digitized image wherein details such as textures or edges are crossed by the scratch. In order to remove the scratch from the digitized image, the pixels which make up the scratch area must be replaced with pixel data which represents, or emulates the original data. In order to effectively repair scratched areas, this pixel data should allow the resulting image to be as sharp in the scratch area as in the surrounding area. Further, continuity of prominent edges should be maintained, and textures created to replace the wire or scratch pixels should match the surrounding texture.
The effectiveness of currently known techniques of digital processing varies according to the features of the image and their relative size within the image at issue and whether they are regularly or randomly occurring. Examples of regularly occurring features include a brick wall or fabric weave texture. Examples of randomly occurring features may include an asphalt roadway or concrete walk or sandy beach. The effectiveness of known techniques also depends upon the size and type of the scratch area. Scratches which show up as small, isolated clusters of noise pixels in smooth or blurred areas of an image are typically relatively easy to remove through known techniques such as filtering or simple cloning and painting techniques. However, existing noise removal techniques fall short where the scratch consists of a plurality of contiguous pixels or falls in a textured area of an image or in areas having prominent edges, or lines.
Currently known techniques of image noise removal can be generally categorized into two types: 1) intra-frame techniques and 2) inter-frame techniques. The difference between these two general types of techniques centers primarily on where data for replacement of noise pixels is obtained from. Inter-frame techniques typically copy pixel data needed to replace noise pixels from preceding or succeeding frames. Intra-frame techniques, on the other hand, typically utilize data within the image frame to be repaired for replacement of noise pixels.
Inter-frame methods typically fail to provide suitable results where the images/scenes at issue reflect an extreme level of camera movement or scene activity. These methods also tend to fall short where the scratch extends across several image frames, or where the damaged image frame is the only image frame available for providing data for repairing the image. Unfortunately, it is common for scratches to run across several image frames, because of the motion of typical motion picture films through a typical motion picture projector. In these situations, corresponding pixel data from a preceding/succeeding image frame is not readily available for replacement/copying to the scratched area.
Known techniques of scratch noise removal have addressed the problem of scratch noise removal in several ways, including: (a) low-pass and other linear filtering (b) median and other non-linear filtering, (c) statistical texture synthesis (d) cloning, i.e. copying another part of the image (e) painting manually (f) projection based methods and (g) methods based on solving simultaneous equations. However, these techniques have been less than successful in providing scratch removal so as to yield optimum results in a variety of scratch/image situations. Every image can be considered to be made up of many different undulating images, each having specific rate and amount by which they undulate. Such an analysis of an image into its component undulating images can be done by a method known as fast fourier transform ("FFT"). When the image is analyzed in this way and the information produced by FFT is manipulated, this is known as working in the frequency domain. When an operation is done to the image itself it is known as an operation in spatial domain.
The methods (a) to (e) suffer from the shortcoming that they work only in one such domain. Frequency domain algorithms can capture global structure of the image but lose local control (line continuity, sharpness). As a result, lines and other details become blurred. One problem shared by all spatial-only methods is that they have local control and information but do not have any information about the global structure of the image. The limitation to a local neighborhood is due to practical computational constraints in some cases. In addition, some of these methods like median and other non-linear filtering are inherently incapable of meaningfully using the global information.
Typically the presence of scratch noise appears as a sudden variation in the pixel intensities at the scratch locations when compared with the surrounding pixel intensity values. This sudden variation appears as high frequency components in the frequency spectrum of a image. By removing higher frequency components, variation in pixel intensity can be reduced to thereby lessen the visibility of the scratch area within the image frame. This operation is known as low-pass filtering and involves transforming the image from the spatial (or image) domain into the frequency domain, filtering out a predetermined level of high frequency components and transforming the resulting image frequencies back into an image. Similar results can be achieved via an operation known as a convolution, which operates on the image directly without first converting it into the frequency domain. Low pass filtering is effective in reducing scratch noise from certain types of images, typically images having few details or smooth textures. This technique is not, however, effective for removing scratch noise from images having textures or very detailed areas or prominent edges. Smoothing by low-pass and similar linear filtering techniques, whereby variations in pixel intensities within a given area are averaged out, is not effective since it often results in reconstructed, or repaired, scratch noise areas being blurred and loss of detail in the repaired scratch area.
With median filtering techniques, a given pixel of a subject image is replaced with the median value of the surrounding pixels. Which pixels comprise the surrounding pixels of a pixel at issue is typically defined by specifying the limits of a window enclosing that pixel. For example a window of 10 pixels by 10 pixels (10.times.10) in which the pixel at issue is located could be used to define the "surrounding" pixels. The surrounding pixels can also be referred to as the "neighborhood" of a given pixel. The size of the window or neighborhood can be varied in accordance with the needs at hand. In applying median filtering to scratch removal where the location of the scratch is known, only the scratch pixels will be replaced by the median value of the surrounding pixels.
Median and similar non-linear filtering techniques work relatively well where the scratch area is limited to a relatively small group of isolated pixels. Typically scratches, and particularly wire noise, consist of many contiguous pixels. As a result, the median value of surrounding pixels is typically the value of the scratch area itself. If a small window, or neighborhood, is chosen, scratches are typically not repaired, since the median value is typically the value of the scratch area itself. In other words, the scratch pixels values are replaced with the value of the scratch pixels. Where a larger window is chosen so as to provide a greater number of surrounding pixels, blurring of the image typically results .
In techniques based on statistical texture synthesis, an area of the damaged image at issue is analyzed and a statistical representation of the image area is developed. This statistical representation is then used to generate a synthesized texture that is similar to the analyzed area . Scratch/wire noise pixels can then be replaced with the synthesized texture. Statistical methods are based on the assumption that the relationship between pixels in a neighborhood has a statistical description which can be discovered by analysis. Thus a given pixel's characteristics are supposed to depend statistically on some or all of its nearby pixels. Where there is a relationship between pixels which are relatively far apart in distance, the neighborhood necessary for analysis of those pixels must be relatively large. An example would be a brick wall with large bricks or a wide wire mesh photographed close-up. Typically in these methods the computational processing required increases as the number of pixels within the neighborhood on which a given pixel depends is increased. As a result these methods are not useful for textures having large features, such as, for example, the texture of an image of a typical brick wall.
Many popular image processing programs, such as for example, Adobe Photoshop.TM., provide a tool for copying pixels from one area of the image to another area. With these types of tools, the area of the image to be copied is typically selected, or defined, via use of a mouse, or other pointer/control device, which allows a user to manipulate a cursor or "brush" on the display screen which displays the image at issue. Using the mouse device, a source area from which pixel data is to be read, or transferred, is defined. Then a destination area to which the pixel data from the source area is to be transferred is defined. "Brush strokes", or movement of the cursor across the destination area, can be accomplished using the mouse. With each "brush stroke" pixels from the source area are copied to the destination area. This method works well when the texture, or pattern, depicted in the image at issue is random or regularly occurring in nature and has relatively small features. Small features might include, for example, spots on a piece of fruit, sand, asphalt of a road, or fabric weave. Where there are, for example, random or regularly occurring details, or patterns, depicted in the image in the form of curved or straight lines then alignment of the edges of the repaired region with that of the surrounding region is very time consuming. Repairing scratches or wires using rubber stamp painting is a task requiring lots of time and skill for many images. Since the human visual system is very sensitive to problems with edges, mismatched edges are relatively easy to pick out by the human eye.
Another technique for scratch removal has been to "paint" over the pixels of the scratch by manually matching the scratch pixels with the surrounding area. This method is very time consuming and the quality of the results obtained depends heavily on the skill of the operator. An even bigger problem is when the image has uneven intensity due to lighting conditions or inter reflections. In such cases, finding the same intensity source area can be difficult. With reference to FIGS. 6(A) and 6(B), such figures illustrate the problems resulting of the simple copying of when attempting to cover up noise in an image with non-uniform shading. Such copying can create misalignment and shading mismatch. In further detail, FIG. 6(A) illustrates an example of noise to be removed or covered up and also illustrates the dotted line region to be copied to cover up such noise. FIG. 6(B) illustrates that the dotted line region has been copied onto the noise. However, the resulting lines are misaligned, and as would be expected because of non-uniform shading, the color of the covered up area is different from that of the surrounding area.
Techniques of scratch noise removal based on projection methods in the context of signal restoration have been previously used. These methods have been used to extend the frequency spectrum of band-limited signals by alternating between signal and transform domains and applying constraints of each domain. The constraints are directed to preservation of known signal values and enforcement of bandlimits. This approach has been generalized through a geometric interpretation which is generally referred to as Projection onto Convex Sets, or POCS. POCS allows the use of any information about the image, such as, for example, the range of luminance values, distinction between defined scratch areas and non-scratch areas, as long as the information can be represented as a closed convex set to be used as a constraint.
In projection based methods an image at issue is projected upon predefined constraints to find another image which closely resembles the image at issue and which is within a defined range of images which satisfy certain pre-defined constraints. The process of finding the closest image satisfying certain pre-defined constraints is known as projecting onto that constraint. Once such an image has been found, this new image, or resultant image, is projected onto the next pre-defined constraint, if any. The constraints represent information that is known about the image. In projection based methods, an image at issue may be considered as a single point in a space which has one or more dimensions. Any point on a flat surface can be described in terms of its X and Y coordinates. Further, any point in a 3-dimensional space, for example a room, can be described in terms of X, Y and Z coordinates. Similarly, an image can be described as a single point in high-dimensional space. For example, an image comprised of 200 pixels by 100 pixels may be represented as a single point having 20,000 dimensions (200.times.100=20,000). Each dimension of the point represents one of the 20,000 pixels which make up the image. The value of each dimension represents the luminance intensity for the given pixel represented by the particular dimension. In typical gray scale imaging, a gray scale of 256 steps is often used for high quality imaging. Thus, the luminance intensity, or value, of a given pixel may range from 0-255, for example.
Through repeated projections onto various constraints, an image can eventually be found that satisfies all of the constraints imposed, simultaneously. The only condition is that the constraints should represent something known as convex sets. The concept of constraints representing convex sets can be explained as follows. When a constraint is placed on, for example, a set of images that are to be considered, the set of images is reduced to a possibly smaller set than the set of all possible images. If this new, smaller set has the property that any linear combination of two images in the set yields an image which is also within the set, then the set is a convex set. This can be expressed as follows: EQU u(x)+(1-u)(y)=z,
where 0.ltoreq.u.ltoreq.1, and x and y are images.
If x and y are two images which are members of a set S, u is a real number between 0 and 1 inclusive, and z is also an image which is a member of the set S, then the set S is a convex set. FIG. 7(A) illustrates a geometrical definition of Equation 1 and how it is satisfied in convex sets but not in concave sets, as shown for example in FIG. 7(B).
In known projection based methods of scratch noise removal, constraints such as bandlimits are imposed. An image is said to be bandlimited if the fourier transform of the image does not have an infinite frequency spectrum. Limiting the frequency band of an image does not provide desirable results in scratch and wire removal from real images.
Other known techniques of scratch removal are based on solving simultaneous equations. These methods typically involve solving numerous simultaneous equations, often as many equations as there are pixels in the image at issue. The computational requirements to carry out this technique can be quite high. Such methods are most useful in removing blur in images. Iterative and non-iterative linear algebra based methods for scratch removal, which require the solution of only a limited number of equations, up to as many equations as there are pixels in the scratch, have been proposed. However, these methods do not work well where the scratch noise at issue consists of a plurality of contiguous pixels as is typically the case with most scratch noise.
A new method described in our recently filed Japanese Patent Application No.P7-303420 (filed on Oct. 30, 1995), which Japanese Patent Application corresponds to U.S. patent application Ser. No. 08/733,753 (filed on Oct. 21, 1996), presents an algorithm for removing such long thin unwanted noise from images. In U.S. patent application Ser. No. 08/733,753, which U.S. patent application is hereby incorporated by reference, we posed the image noise removal problem as follows:
Given (i) the locations of noisy pixels and (ii) a prototype (sample) image, it is possible to restore those noisy pixels in a natural way.
In our method described in U.S. patent application Ser. No. 08/733,753 the user specifies (a) the location of the noisy pixels by painting a mask (called noise mask) over the noise area using a digital paint brush like tool, (b) an area around the noise (called repair subimage), and (c) an area from a non noisy region to be used as a prototype (called sample subimage). FIG. 1 illustrates an example image with noise. FIG. 2 illustrates a noise mask painted on the noise. FIG. 3 illustrates an example of sample and repair subimage selection.
The embodiments of our U.S. patent application Ser. No. 08/733,953 use spatial and frequency domain information from the sample and repair subimages to remove the noise. In contrast, previous popular approaches like copy-pasting, painting, median filtering and low pass filtering, etc. work only in one domain. Although the results from the method in U.S. patent application Ser. No. 08/733,953 are better than previously known methods, our method in U.S. patent application Ser. No. 08/733,953 was not designed for images which have tremendous intensity variation across their the area of such images.
The present invention seeks to overcome the shortcomings set forth above and to provide methods and apparatus of removing scratch noise from digitized photographic images which yield high quality results without the need for undue operator manipulation.